#include<bits/stdc++.h>
#include "game.h"
#define ll long long
#define L x<<1
#define R x<<1|1
#define mid (l+r>>1)
#define lc L,l,mid
#define rc R,mid+1,r
#define OK Ll<=l&&r<=Rr
#define Root 1,1,n
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
#define pb push_back
#define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i])
#define E(x) for(auto y:p[x])
#define Pi pair<int,int>
#define ui unsigned ll
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
inline void pf(int x){if(x<0) putchar('-'),x=-x;if(x>9)pf(x/10);putchar(x%10+48);}
using namespace std;
const int N=6e5+5,M=1e7+5,inf=(1LL<<31)-1,mod=1e9+7;
const ll llf=1e18;
inline void add(int &a,int b){((a+=b)>=mod) and (a-=mod);}
inline int Add(int a,int b){return add(a,b),a;}
inline int mul(int a,int b){return 1LL*a*b%mod;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline void red(int &a,int b){add(a,mod-b);}
inline int Red(int a,int b){return red(a,b),a;}
inline int qp(int a,int b){if(!b)return 1;int c=qp(a,b>>1);Mul(c,c);if(b&1)Mul(c,a);return c;}
inline int INV(int x){return qp(x,mod-2);}
int h[N],to[M],nxt[M],cnt,m,k;
bool v[N];
inline void add_(int a,int b){
	to[++cnt]=b,nxt[cnt]=h[a],h[a]=cnt;
	// if(a<b)cerr<<(a-1)/k+1<<','<<(a-1)%k+1<<"->"<<(b-16-1)/k+1<<','<<(b-16-1)%k+1<<'\n';
	// cerr<<a<<"->"<<b<<'\n';
}//a->b,a选1,b就得选1
int dfn[N],low[N],Time,tot,bel[N],s[N],tp;
bool instac[N];
inline void tarjan(int x){
	dfn[x]=low[x]=++Time,s[++tp]=x,instac[x]=1;
	e(x)if(!dfn[y])tarjan(y),low[x]=min(low[x],low[y]);
	else if(instac[y])low[x]=min(low[x],dfn[y]);
	if(low[x]==dfn[x]){
		tot++;
		for(int z=s[tp--];;z=s[tp--]){
			instac[z]=0,bel[z]=tot;
			if(z==x)return;
		}
	}
}
inline int id(int x,int y,int ty){
	return ty*m+(x-1)*k+y;
}
struct node{
	int x,key;
}a[N];
inline bool cmp(node a,node b){
	return a.key<b.key;
}
mt19937 rd(1145141);
vector<int> guess(int n,int limit){
	vector<int>p;
	p.resize(n);
	k=n,m=n*n;
	if(n<=9&&limit==1000000){
		repn(i)p[i-1]=i;
		do{
			if(count(p)==n)return p;
		}while(next_permutation(p.begin(),p.end()));
	}
	repn(i)repn(j)repn(k)if(j^k)add_(id(i,j,1),id(i,k,0));
	repn(i)repn(j)repn(k)if(i^j)add_(id(i,k,1),id(j,k,0));
	int T=10;
	if(limit==1000000)T=25;
	if(limit==20000)T=1;
	while(T--){
	repn(i)a[i].x=i,a[i].key=rd();
	sort(a+1,a+n+1,cmp);
	repn(i)p[i-1]=a[i].x;
	int K=count(p);
	repn(i)rep(j,i+1,n){
		int x=p[i-1],y=p[j-1];
		swap(p[i-1],p[j-1]);
		int w=count(p)-K;
		if(w==2){
			add_(id(i,y,0),id(i,y,1));
			add_(id(j,x,0),id(j,x,1));
		}else if(w==-2){
			add_(id(i,x,0),id(i,x,1));
			add_(id(j,y,0),id(j,y,1));
		}else if(w==1){
			add_(id(i,x,1),id(i,x,0));
			add_(id(j,y,1),id(j,y,0));
			add_(id(i,y,1),id(j,x,0));
			add_(id(j,x,0),id(i,y,1));
			add_(id(j,x,1),id(i,y,0));
			add_(id(i,y,0),id(j,x,1));
		}else if(w==-1){
			swap(x,y);
			add_(id(i,x,1),id(i,x,0));
			add_(id(j,y,1),id(j,y,0));
			add_(id(i,y,1),id(j,x,0));
			add_(id(j,x,0),id(i,y,1));
			add_(id(j,x,1),id(i,y,0));
			add_(id(i,y,0),id(j,x,1));
		}else {
			//没变
			add_(id(i,y,1),id(i,y,0));
			add_(id(j,x,1),id(j,x,0));
			add_(id(i,x,1),id(i,x,0));
			add_(id(j,y,1),id(j,y,0));
		}
		swap(p[i-1],p[j-1]);
	}
	}
	rep(i,1,m<<1)if(!dfn[i])tarjan(i);
	repn(i)repn(j)if(bel[id(i,j,1)]<bel[id(i,j,0)])p[i-1]=j;
	return p;
}
/*
4 1000001
2 4 3 1
3 1000001
1 2 3
10 1000000
1 2 3 4 5 6 7 8 9 10
*/